\chapter{密钥管理(Key Management)}
密钥管理是一个很大的话题，其涉及到\footnote{对这些密钥管理内容的简单解释，可以参考\url{https://baike.baidu.com/item/密钥管理},百度的这个词条由“科普中国”科学百科词条编写与应用工作项目审核 。}：
\begin{enumerate}
	\item 密钥生成 
	\item 密钥分发 
	\item 验证密钥 
	\item 更新密钥 
	\item 密钥存储 
	\item 备份密钥 
	\item 密钥有效期 
	\item 销毁密钥 
\end{enumerate}
\par

图\ref{key-management}是来自于简书上一个帖子里的一张图，内容比上面多了一项“密钥使用”其他都一样，只不过叫法略有不同，大家参考对比来学习。
\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{keymgm.png}
	\caption{密钥管理的主要内容\footnote{本图来自\url{https://www.jianshu.com/p/46a911bd49a7}}}
	\label{key-management}
\end{figure}
\par

因为密钥的安全在现在的密码体制安全中是决定性的，所以美国的NIST也就密钥管理，发布了一些标准，比如SP 800-57 Recommendation for Key Management: Part 1 – General，Part 2 – Best Practices for Key Management Organizations，Part 3: Application-Specific Key Management Guidance等，在SP 800-57 Part1中，其从几个侧面讨论了密钥管理，可以从NIST SP 800-57 Part 1的目录上看到，标准的第5部分介绍了一般密钥管理要求，如图\ref{SP800-57-5}所示，第6部分介绍了密钥信息的保护需求，如图\ref{SP800-57-6}所示，第7部分介绍了密钥生命周期的几个阶段，如图\ref{SP800-57-7}所示，第8部分介绍了密钥管理的各个阶段，如图\ref{SP800-57-8}所示，第9部分对CKMS(Cryptographic Key Management System)系统的安全要求进行了说明，如图\ref{SP800-57-9}所示。
\footnote{Accountability,常见的翻译有可检查性、可核查性、可问责、可追溯性}
\par

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.8\textwidth]{NIST-SP-800-57-KEYMAN-5.png}
	\caption{NIST SP 800-57一般密钥管理要求}
	\label{SP800-57-5}
\end{figure}

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.8\textwidth]{NIST-SP-800-57-KEYMAN-6.png}
	\caption{NIST SP 800-57密钥信息的保护需求}
	\label{SP800-57-6}
\end{figure}

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.5\textwidth]{NIST-SP-800-57-KEYMAN-7.png}
	\caption{NIST SP 800-57密钥生命周期}
	\label{SP800-57-7}
\end{figure}

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.5\textwidth]{NIST-SP-800-57-KEYMAN-8.png}
	\caption{NIST SP 800-57密钥管理的各个阶段}
	\label{SP800-57-8}
\end{figure}

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.8\textwidth]{NIST-SP-800-57-KEYMAN-9.png}
	\caption{NIST SP 800-57CKMS系统的安全要求}
	\label{SP800-57-9}
\end{figure}

\newpage

\section{密钥分发(key distribution)的基本方法}
加密算法中密钥非常关键，而密钥或者生成密钥的相关信息是需要在通信双方或多方之间传递的，那么如何安全地对密钥或者密钥相关信息进行相互之间的传递就是一个重要的问题，这也是密钥分发研究的问题。

\subsection{有中心的密码分发}
我们假定有个一个密钥分配中心KDC(key distribution center)与所有的通信方之间都有一个主密钥(可以说建立了一个可信信道)，比如A和KDC之间的主密钥为$K_A$，B和KDC之间的主密钥为$K_B$，C和KDC之间的主密钥为$K_C$等等。A如果想和B建立一个会话密钥(session key) $K_S$的过程为：
\begin{enumerate}
	\item A向KDC发送请求和B建立会话密钥的请求消息R和一个随机数$N_1$.
	\item KDC将会话密钥$K_S$，应答消息，$N_1$，$E_{K_B}(K_S,ID_A)$一起用$K_A$加密，发送给A，其中$ID_A$是A的身份信息。
	\item A用$K_A$解密后，比较$N_1$确定是本次请求，然后将$E_{K_B}(K_S,ID_A)$发送给B。
	\item B收到后用$K_B$解密，然后生成一个新随机数$N_2$，将$E_{K_S}(N_2)$发送给A。
	\item A用$K_S$解密后，将$E_{K_S}(f(N_2))$发送给B，A和B的会话密钥A方已经确认。
	\item B用$K_S$解密后，验证$f(N_2))$，正确，则A和B的会话密钥B方已经确认。
\end{enumerate}
把以上的过程用一个符号体系来表述：
\begin{enumerate}
	\item $A\rightarrow KDC :: R,N_1$
	\item $KDC\rightarrow A :: E_{K_A}(K_S,N_1,E_{K_B}(K_S,ID_A))$
	\item $A :: D_{K_A}(E_{K_A}(K_S,N_1,E_{K_B}(K_S,ID_A))),J(N_1)$\footnote{$J(N_1)$表示判断$N_1$是否与其生成的一直，防止重放攻击}\\
	      $A\rightarrow B :: E_{K_B}(K_S,ID_A)$
	\item $B\rightarrow A :: E_{K_S}(N_2)$
	\item $A\rightarrow B :: E_{K_S}(f(N_2))$
	\item $B :: J(f(N_2))$
\end{enumerate}

\subsection{无中心的密钥分发}
无中心的密钥分发要求双方已经共享了一个主密钥(main key)MK，再此基础上，A、B双方协商一个新的通信密钥(session key) SK，协商过程如下：
\begin{enumerate}
	\item A向B发送请求密钥消息R和一个随机数$N_1$.
	\item B选取会话密钥$SK$,将其和B的身份、$f(N_1)$、新随机数$N_2$用$MK$加密后一起发给A。
	\item A收到后，用$MK$解密，验证$f(N_1)$，证明是此次的协商。A将$SK$和$f(N_2)$用$MK$加密后发给B。A与B的新会话开始使用$SK$。
	\item B收到后，用$MK$解密，验证$f(N_2)$，B与A的新会话开始使用$SK$,
\end{enumerate}
把以上的过程用一个符号体系来表述：
\begin{enumerate}
	\item $A\rightarrow B :: R,N_1$.
	\item $B\rightarrow A :: E_{MK}(SK,ID_B,f(N_1),N_2)$
	\item $A :: V(f(N_1))$\footnote{$V(f(N_1))$表示验证(validate)$f(N_1)$}\\
	      $A\rightarrow B :: E_{MK}(SK,f(N_2))$
	\item $B :: V(f(N_2))$
\end{enumerate}
A、B协商成功新的会话密钥SK。
\newpage

\section{Diffie-Hellman密钥交换}
大素数p和p的原根a\footnote{ $a^{\phi{p}}\pmod{p}=1$，p为素数，所以有$a^{p-1}\pmod{p}=1$}公开，在这一基础上通信双方就可以协商会话密钥，过程如下：
\begin{enumerate}
	\item A选择一个保密随机数$X_A$，将$\alpha=a^{X_A}\ mod\ p$发给B。
	\item B选择一个保密随机数$X_B$，将$\beta=a^{X_B}\ mod\ p$发给A。
	\item A,B可分别计算密钥，A的计算过程为，$\beta ^{X_A}=a^{X_B X_A}\ (mod\ p)$,B的计算过程为，$\alpha ^{X_B}=a^{X_A X_B}\ (mod\ p)$。
\end{enumerate}

\subsection{DH中间人攻击}
假设在A和B协商密钥的时候，有个攻击者Mallory(记为M)，可以形成中间人攻击(Man-in-the-middle attack,缩写MITM)，其过程如下：
\begin{enumerate}
	\item $A :: X_A$\\
	      $A \rightarrow M :: \alpha=a^{X_A} \pmod{p}$
	      
	\item $M :: X_{MA},X_{MB}$\\
	      $M \rightarrow B :: \beta'=a^{X_{MB}} \pmod{p}$\\
	      $M \rightarrow A :: \alpha'=a^{X_{MA}} \pmod{p}$
	      
	\item $B :: X_B$\\
	      $B\rightarrow M :: \beta=a^{X_B} \pmod{p}$
	      
	\item $A :: \alpha ^{X_{MA}}=a^{X_A X_{MA}} \pmod{p})$\\
	      $B :: \beta ^{X_{MB}}=a^{X_B X_{MB}} \pmod{p} $\\
	      $M :: \alpha'^{X_A}=a^{X_{MA} X_A} \pmod{p},\beta'^{X_{B}}=a^{X_{MB} X_B} \pmod{p}$
\end{enumerate}
从以上密钥交换的过程可以看出，最终A和M之间形成一个密钥，M和B之间形成一个密钥，而A以为和B在通信，B以为和A在通信。\par

Diffie-Hellman协议之所以不能抵抗中间人攻击，是因为在通信过程中并没有对参与方进行认证，可以在密钥交换过程中加入认证技术来抵抗中间人攻击。

\newpage

\section{密钥分割}
在有些应用场合，为了保证密钥的安全，需要密钥(或者秘密)由多人持有，任何一个人持有的信息不能得到完整的密钥，只有全部或达到规定的人数时，将这些人持有的信息合并，才可以获得(或者计算)完整的密钥。
\subsection{Shamir门限方案}
Shamir门限方案时基于多项式的拉格朗日(Lagrange)插值公式的。
\begin{note}
	Shamir这个名字是不是很熟悉？他就是RSA中的S，Shamir.图灵将获得者Shamir,Shamir门限方案也是其获得图灵奖时提到的主要贡献\footnote{关于Shamir的简单介绍，可以看ACM关于图灵机获得者的介绍页面\url{https://amturing.acm.org/award_winners/shamir_2327856.cfm}}。
\end{note}

\subsubsection{拉格朗日插值法(Lagrange Interpolation Polynomial )}
在数值分析中，拉格朗日插值法是以法国十八世纪数学家约瑟夫·拉格朗日命名的一种多项式插值方法。许多实际问题中都用函数来表示某种内在联系或规律，而不少函数都只能通过实验和观测来了解。如对实践中的某个物理量进行观测，在若干个不同的地方得到相应的观测值，拉格朗日插值法可以找到一个多项式，其恰好在各个观测的点取到观测到的值。这样的多项式称为拉格朗日（插值）多项式。数学上来说，拉格朗日插值法可以给出一个恰好穿过二维平面上若干个已知点的多项式函数。拉格朗日插值法最早被英国数学家爱德华·华林于1779年发现\footnote{E. Waring. Problems Concerning Interpolations. Philosophical Transactions of the Royal Society of London. 1779, 69: 59–67.}，不久后（1783年）由莱昂哈德·欧拉再次发现。1795年，拉格朗日在其著作《师范学校数学基础教程》中发表了这个插值方法，从此他的名字就和这个方法联系在一起\footnote{E. Meijering. A chronology of interpolation: From ancient astronomy to modern signal and image processing,. Proceedings of the IEEE: 323.}。\footnote{此段文字引自\url{https://www.cnblogs.com/ECJTUACM-873284962/p/6833391.html}，引用这段文字的原因是，这段文字里面有参考文献的引用，本人没有去考证。}\par

拉格朗日插值多项式\footnote{\url{https://mathworld.wolfram.com/LagrangeInterpolatingPolynomial.html}}：
\[P\left( x\right) =\sum_{j=1}^{n}P_j\left( x \right)  \]
此多项式代表的曲线通过n个点$\left( x_1,y_1=f(x_1)  \right), \left( x_2,y_2=f(x_2)  \right),\ldots,\left( x_n,y_n=f(x_n)  \right) $,此处：
\[ P_j\left( x \right) = y_j \prod_{k=1;k\neq j}^{n}\frac{x-x_k}{x_j-x_k} \]
把拉格朗日插值多项式展开写：\\
$
P(x) =  y_1 \dfrac{(x-x_2)(x-x_3)\ldots (x-x_n)}{(x_1-x_2)(x_1-x_3)\ldots (x_1-x_n)} + y_2 \dfrac{(x-x_1)(x-x_3)\ldots (x-x_n)}{(x_2-x_2)(x_2-x_3)\ldots (x_2-x_n)} + \\
\\
 \ldots + y_n \dfrac{(x-x_1)(x-x_2)\ldots (x-x_{n-1})}{(x_n-x_2)(x_n-x_3)\ldots (x_n-x_{n-1})} 
$
\par

利用$f(x)$的n个采样点构造拉格朗日多项式$P(x)$，以此来拟合$f(x)$。\par

\subsubsection{门限方案}
假设有n个参与者，选择一个大素数q，$q \geq n+1$，在$GF(q)\setminus {0}$上取随机数$a_0$，在有限域$GF(q)$上构造一个多项式：
\[f(x) =a_0 + a_1 x^1 + a_2 x^2+\ldots + a_{k-1}x^{k-1}  \pmod{q}\]
其中k-1个系数$a_1,a_2,\ldots,a_{k-1}$也是在$GF(q)\setminus {0}$上选取。\par
把$a_0$做为密钥S，n个参与者分到的子密钥分别为$f(1),f(2),\ldots,f(n)$,任意k个参与者合作都可以获得密钥S，方法是利用他们的k个子密钥$(k_i,f(k_i)),i=1,2,\ldots,k$，其中，$k_i\in \left\lbrace 1,2,\ldots,n \right\rbrace $,构造拉格朗日插值多项式：
\[P\left( x\right) =\sum_{j=1}^{k} f(k_j) \prod_{i=1;i\neq j}^{k} \frac{x-x_i}{x_j-x_i} \pmod{q} \]
通过多项式$P(x)$可以直接计算获得密钥$S=P(0)$.而当想共同获得密钥的参与者少于k时，其无法获得密钥。

\subsection{CRT门限方案}
CRT(chinese remainder theorem)门限方案，顾名思义，时利用中国剩余定理构造的门限方案。

\subsubsection{中国剩余定理\cite{lxfFoCysMath}}
设$m_1,m_2,\ldots,m_k$是k个两两互素的正整数，若令$m=m_1 m_2\ldots m_k, M_i = m_1m_2\ldots m_{i-1} m_{i+1}\ldots m_k,m=m_i M_i$,则对于任意的整数$b_1,b_2,\ldots,b_k$,同余方程组\\
\begin{center}
	$
	\begin{cases}
	x \equiv b_1 (mod\ m_1)\\
	x \equiv b_1 (mod\ m_1)\\
	\ldots \\
	x \equiv b_k (mod\ m_k)\\
	\end{cases}
	$
\end{center}
有唯一解$x \equiv M'_1 M_1 b_1 + M'_2 M_2 b_2 +\ldots + M'_k M_k b_k (mod\ m)$,其中$M'_i$为$M_i$的逆元，$M'_i M_i \equiv 1 (mod\ m_i),i=1,2,\ldots,k$ 。

\subsubsection{门限方案}
Asmuth和Bloom在其1980发表的文章"A Modular Approach to Key Safeguarding"一文中提出了一个基于中国剩余定理的密码共享方案。\cite{Denning-cry}\par

假设共有n个参与者，取n个大于1的整数$m_1,m_2,\ldots,m_n$，满足$m_1 \leq m_2\leq \ldots \leq m_n$,$gcd(m_i,m_j)=1,\forall i,j,i \neq j$(即两两互素),$m_1 m_2 \ldots m_k >p m_n m_{n-1} m_{n-k+2}$,其中p和$m_i(i=1,\ldots,n)$互素, 计算$M=m_1 m_2 \ldots m_n$，随机取一数S做为密钥，$m_1 m_2 \ldots m_k >S> m_n m_{n-1} m_{n-k+2}$，将$\left( s_i,m_i,M \right) (i=1,\ldots,n)$做为子密钥分别发给n个参与者，其中$s_i=S \pmod{m_i}$,至此我们构建了一个基于CRT的(k,n)门限方案。\par

每个参与者i都可以计算:\\
\begin{center}
	$
	\begin{cases}
		M_i = \frac{M}{m_i} (mod\ m_1)\\
		M_i^{'} = M_i^{-1} (mod\ m_i)\\
	\end{cases}
	$
\end{center}
\par
现在有k个参与者想要恢复密钥S，他们的私钥记为$\left( s_{c_i},m_{c_i},M \right) (i=1,\ldots,k;c_i \in \left( 1,2,\ldots,n \right) )$，我们有：\\
\begin{center}
	$
	\begin{cases}
		S \equiv s_{c_1} \pmod{m_{c_1}}\\
		\ldots \\
		S \equiv s_{c_k} \pmod{m_{c_k}}\\
	\end{cases}
	$
\end{center}
根据中国剩余定理我们可得：
\[S = \sum_{j=1}^{k} s_{c_j} M_{c_j} M_{c_j}^{'} s_{c_j} \pmod{\prod_{i=1}^{k} m_{c_i} } \]
从而这k个参与这把子密钥信息联合可计算密钥S。\par

而当少与k个人合作时，比如k-1个人，我么可以得到方程组：\\
\begin{center}
	$
	\begin{cases}
	x \equiv s_{c_1} \pmod{m_{c_1}}\\
	\ldots \\
	x \equiv s_{c_{k-1}} \pmod{m_{c_{k-1}}}\\
	\end{cases}
	$
\end{center}
利用CRT定理，我么可得方程解为：
\[S^{'}=x = \sum_{j=1}^{k-1} s_{c_j} M_{c_j} M_{c_j}^{'} s_{c_j} \pmod{\prod_{i=1}^{k-1} m_{c_i} } \]

我们有：
\[ m_1 m_2 \ldots m_k >S>p m_n m_{n-1} m_{n-k+2}> \prod_{i=1}^{k-1} m_{c_i} > S^{'}\]
显然$S\neq S^{'}$.